package J20250121_Dynamic;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划51——54
 * User: 王圆豪
 * Date: 2025-02-17
 * Time: 22:47
 */
public class Solution8 {
    //⽬标和——https://leetcode.cn/problems/target-sum/
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int l : nums) sum += l;
        if((sum + target) % 2 != 0) return 0;
        int a = (target + sum) / 2;
        if(a < 0) return 0;
        int[] dp = new int[a+1];
        dp[0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = a; j >= nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[a];
    }

    //最后⼀块⽯头的重量II——https://leetcode.cn/problems/last-stone-weight-ii/
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int a : stones) sum += a;
        int m = sum / 2;
        int[] dp = new int[m+1];
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= 0; j--){
                dp[j] = dp[j];
                if(j - stones[i-1] >= 0){
                    dp[j] = Math.max(dp[j], dp[j-stones[i-1]] + stones[i-1]);
                }
            }
        }
        return sum - 2*dp[m];
    }

    //完全背包——https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        int[] v = new int[n];
        int[] w = new int[n];
        for(int i = 0; i < n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int ret1 = prefectBag1(n,V,v,w);
        int ret2 = prefectBag2(n,V,v,w);
        System.out.println(ret1);
        System.out.println(ret2);
    }

    public static int prefectBag2(int n, int V, int[] v, int[] w){
        int[] dp = new int[V+1];
        for(int i = 1; i <= V; i++) dp[i] = -1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= V; j++){
                if(j >= v[i-1] && dp[j-v[i-1]] != -1){
                    dp[j] = Math.max(dp[j], dp[j-v[i-1]] + w[i-1]);
                }
            }
        }
        return dp[V] == -1 ? 0 : dp[V];
    }

    public static int prefectBag1(int n, int V, int[] v, int[] w){
        int[][] dp = new int[n+1][V+1];
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= V; j++){
                for(int k = 0; j - k*v[i-1] >= 0; k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*v[i-1]] + k*w[i-1]);
                }
            }
        }
        return dp[n][V];
    }

    //零钱兑换——https://leetcode.cn/problems/coin-change/description/
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for(int i = 1; i <= amount; i++) dp[0][i] = 0x3f3f3f3f;

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1]){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-coins[i-1]] + 1);
                }
            }
        }
        return dp[n][amount] >= 0x3f3f3f3f ? -1 : dp[n][amount];
    }
}
